//实现 strStr() 函数。 
//
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
//果不存在，则返回 -1 。 
//
// 
//
// 说明： 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "hello", needle = "ll"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：haystack = "aaaaa", needle = "bba"
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：haystack = "", needle = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= haystack.length, needle.length <= 5 * 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
// Related Topics 双指针 字符串 字符串匹配 👍 1339 👎 0

package leetcode.editor.cn;

class ImplementStrstr {
    public static void main(String[] args) {
        Solution solution = new ImplementStrstr().new Solution();
        solution.strStr("aabaabaafa", "aabaaf");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int strStr(String haystack, String needle) {
            // 先判断模式串是否为0
            if (needle.length() == 0) {
                return 0;
            }

            int[] next = new int[needle.length()];
            getNext(next, needle);  // 获取模式串的next数组

            int j = 0;  // next数组中初始位置为0
            for (int i = 0; i < haystack.length(); i++) {
                while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                    j = next[j - 1];
                }

                if (haystack.charAt(i) == needle.charAt(j)) {
                    j++;
                }

                if (j == needle.length()) {
                    return i - needle.length() + 1;
                }
            }

            return -1;
        }

        */

        /**
         * 生成next数组，（不减一的代码实现）
         *
         * @param next
         * @param s
         *//*
        public void getNext(int[] next, String s) {
            // j从0开始，此时next数组初始化
            int j = 0;
            next[0] = 0;
            for (int i = 1; i < s.length(); i++) {
                // j要保证大于0，因为下面有取j-1作为数组下标的操作
                while (j > 0 && s.charAt(i) != s.charAt(j)) {
                    // 查找前一位对应的回退位置
                    j = next[j - 1];
                }

                // 相等即向后移动
                if (s.charAt(i) == s.charAt(j)) {
                    j++;
                }

                next[i] = j;    // 将j(前缀的长度)赋值给next[i]
            }
        }*/

//        public int strStr(String haystack, String needle) {
//            // 先判断模式串是否为0
//            if (needle.length() == 0) {
//                return 0;
//            }
//
//            int[] next = new int[needle.length()];
//            getNext(next, needle);  // 获取模式串的next数组
//
//            int j = -1;  // next数组中初始位置为0
//            for (int i = 0; i < haystack.length(); i++) {
//                while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
//                    j = next[j];
//                }
//
//                if (haystack.charAt(i) == needle.charAt(j + 1)) {
//                    j++;
//                }
//
//                if (j == needle.length() - 1) {
//                    return i - needle.length() + 1;
//                }
//            }
//
//            return -1;
//        }
//
//        /**
//         * 前缀表减一的实现
//         *
//         * @param next
//         * @param s
//         */
//        public void getNext(int[] next, String s) {
//            // j从0开始，此时next数组初始化
//            int j = -1;
//            next[0] = j;
//            for (int i = 1; i < s.length(); i++) {
//                // j要保证大于等于0，因为下面有取j作为数组下标的操作
//                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
//                    // 查找前一位对应的回退位置
//                    j = next[j];
//                }
//
//                // 相等即向后移动
//                if (s.charAt(i) == s.charAt(j + 1)) {
//                    j++;
//                }
//
//                next[i] = j;    // 将j(前缀的长度)赋值给next[i]
//            }
//        }
/*        public int strStr(String haystack, String needle) {
            int[] next = new int[needle.length()];
            getNext(next, needle);
            int j = -1;
            for (int i = 0; i < haystack.length(); i++) {
                while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                    j = next[j];
                }

                if (haystack.charAt(i) == needle.charAt(j + 1)) {
                    // i++在for中
                    j++;
                }

                if (j == next.length - 1) {
                    return i - next.length + 1;
                }
            }
            return -1;
        }


        */

        /**
         * 求模式串的next数组(减一的next[]数组)
         *
         * @param next
         * @param s
         *//*
        public void getNext(int[] next, String s) {
            int j = -1;
            next[0] = j;
            // 从一开始，此时 j+1 = 0，i在j后面一位，进行匹配
            for (int i = 1; i < s.length(); i++) {
                // 注意j加一来匹配，因为是减一的next1组
                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                    j = next[j];
                }

                // 匹配则共同移动
                if (s.charAt(i) == s.charAt(j + 1)) {
                    // i++在for循环中
                    j++;
                }

                next[i] = j;
            }
        }*/
        /*public int strStr(String haystack, String needle) {
            int[] next = new int[needle.length()];
            getNext(next, needle);
            int j = 0;
            for (int i = 0; i < haystack.length(); i++) {
                while (j >= 0 && haystack.charAt(i) != needle.charAt(j)) {
                    j = next[j - 1];
                }

                if (haystack.charAt(i) == needle.charAt(j)) {
                    // i++在for中
                    j++;
                }

                if (j == next.length - 1) {
                    return i - next.length + 1;
                }
            }
            return -1;
        }

        */

        /**
         * 求模式串的next数组(不减一的next[]数组)
         *//*
        public void getNext(int[] next, String s) {
            int j = 0;
            next[0] = j;
            for (int i = 1; i < s.length(); i++) {
                while (j >= 0 && s.charAt(i) != s.charAt(j)) {
                    j = next[j - 1];
                }

                if (s.charAt(i) == s.charAt(j)) {
                    j++;
                }

                next[j] = j;
            }
        }*/
        public int strStr(String haystack, String needle) {
            int[] next = getNext(needle);
            int j = -1;
            for (int i = 0; i < haystack.length(); i++) {
                while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                    j = next[j];
                }

                if (haystack.charAt(i) == needle.charAt(j + 1)) {
                    j++;
                }

                if (j == needle.length() - 1) return i - needle.length() + 1;
            }
            return -1;
        }

        // 前缀表减一的实现
        public int[] getNext(String s) {
            char[] arr = s.toCharArray();
            int[] next = new int[arr.length];
            int j = -1;
            next[0] = j;
            for (int i = 1; i < arr.length; i++) {
                while (j >= 0 && arr[i] != arr[j + 1]) {
                    j = next[j];
                }

                if (arr[i] == arr[j + 1]) {
                    j++;
                }

                next[i] = j;
            }

            return next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
